#define _CRT_SECURE_NO_WARNINGS 1
struct Node* BuyNewNode(int x)
{
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    if (node == NULL)
    {
        perror("malloc:");
    }

    node->val = x;
    node->next = NULL;

    return node;
}

void insert(struct Node** phead, struct Node* pos, int x)
{
    struct Node* n = pos->next;
    struct Node* node = BuyNewNode(x);
    pos->next = node;
    node->next = n;

}

struct Node* copyRandomList(struct Node* head)
{
    if (head == NULL)
        return head;

    struct Node* pos = head;
    while (pos)
    {
        insert(&head, pos, pos->val);
        pos = pos->next->next;
    }

    struct Node* cur = head;

    while (cur)
    {
        if (cur->random == NULL)
        {
            cur->next->random = NULL;
            cur = cur->next->next;
        }
        else
        {
            cur->next->random = cur->random->next;
            cur = cur->next->next;
        }
    }

    struct Node* chead = head->next;
    cur = head->next;

    while (cur->next != NULL)
    {
        cur->next = cur->next->next;
        cur = cur->next;
    }

    return chead;


}